home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / b_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  1.6 KB  |  85 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  b_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_BHEAP_H
  17. #define LEDA_BHEAP_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // b_heap: bounded heaps with integer keys in [a..b]
  21. //------------------------------------------------------------------------------
  22.  
  23. #include <LEDA/basic.h>
  24. #include <LEDA/list.h>
  25. #include <LEDA/array.h>
  26.  
  27. class b_heap_node {
  28.  
  29. friend class b_heap;
  30. friend void print_b_heap_item(b_heap_node*);
  31.  
  32. int key;
  33. GenPtr info;
  34. list_item loc;
  35.  
  36. b_heap_node(int k, GenPtr i ) 
  37. { 
  38.   key = k; info = i; loc = 0; }
  39.  
  40.   LEDA_MEMORY(b_heap_node)
  41.  
  42. };
  43.  
  44. typedef b_heap_node* b_heap_item;
  45.  
  46. typedef list<b_heap_item>* b_heap_bucket;
  47.  
  48.  
  49. class b_heap {
  50.  
  51.     int min;
  52.     int max;
  53.     int low;
  54.     int high;
  55.     
  56.     array<b_heap_bucket>  T;
  57.  
  58.  
  59. public:
  60.  
  61. b_heap(int a, int b);
  62. ~b_heap() { clear(); }
  63. b_heap_item insert(int key, GenPtr info) ;
  64.  
  65. b_heap_item find_min();
  66. b_heap_item find_max();
  67. GenPtr del_min();
  68. GenPtr del_max();
  69. b_heap_item decrease_key(b_heap_item it, int k);
  70. b_heap_item increase_key(b_heap_item it, int k);
  71.  
  72. void delete_item(b_heap_item it);
  73. void clear();
  74.  
  75. GenPtr info(b_heap_item it) { return it->info; }
  76. int key(b_heap_item it)  { return it->key; }
  77. int empty()              { return (find_min()==0) ? true : false; }
  78.  
  79. void print();
  80.  
  81. };
  82.  
  83. #endif
  84.  
  85.